package searching;

import junit.framework.Assert;

public class search {

	/**
	 * @param args
	 */
	public static void main(String[] args) 
	{
		FindSmallestInRotatedSortedArray();

	}
	
	
	public static void  FindSmallestInRotatedSortedArray()
	{
		int[] array = {13,14,15,17,19,21,23, 1,3,4,5,6,7,8,7,8,9,10};
		
		int expected = 7;
		int actual = FindSmallestInRotatedSortedArray(array, 0, array.length-1);
		
		Assert.assertEquals(expected, actual);
	}
	private static int FindSmallestInRotatedSortedArray(int[] a, int left, int right)
	{
		if(left == right)
			return left;
		if(left == right-1)
		{
			// comparison for unrotated sorted array case, for rotated array, we could ways return "right"
			// because we know the last two element is always like "23 1" as we always search in unsorted half
			return a[right] < a[left] ? right : left;
		}
		int mid = (left + right) /2;
		
		// idea always search in the unsorted half, that's where our target is
		// right half is unsorted, our target is in right half, search right again
		if(a[right] < a[mid])
		{
			return FindSmallestInRotatedSortedArray(a, mid, right);
		}
		// right half sorted, left half unsorted, search left 
		else
		{
			return FindSmallestInRotatedSortedArray(a, left, mid);
		}
	}
	
	public static int BinarySearch(int[] sortedArray)
	{
		return 0;
	}
	
	public static int DFS(int[] sortedArray)
	{
		return 0;
	}
	
	public static int BFS(int[] sortedArray)
	{
		return 0;
	}

}
